Bell number

 ( Integer Sequences ) 

In combinatorics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

The Bell numbers are denoted $B\_n$, where $n$ is an integer greater than or equal to zero. Starting with $B\_0\; =\; B\_1\; =\; 1$, the first few Bell numbers are

$1,\; 1,\; 2,\; 5,\; 15,\; 52,\; 203,\; 877,\; 4140,\; \backslash dots$ .

The Bell number $B\_n$ counts the different ways to partition a set that has exactly $n$ elements, or equivalently, the equivalence relations on it. $B\_n$ also counts the different for $n$-line poems.

As well as appearing in counting problems, these numbers have a different interpretation, as moments of probability distributions. In particular, $B\_n$ is the $n$-th moment of a Poisson distribution with mean 1.

---

Counting

---

Set partitions In general, $B\_n$ is the number of partitions of a set of size $n$. A partition of a set $S$ is defined as a family of nonempty, pairwise disjoint subsets of $S$ whose union is $S$. For example, $B\_3\; =\; 5$ because the 3-element set $\backslash \{a,b,c\backslash \}$ can be partitioned in 5 distinct ways:

$\backslash \{\; \backslash \{a\backslash \},\; \backslash \{b\backslash \},\; \backslash \{c\backslash \}\; \backslash \},$

$\backslash \{\; \backslash \{a\backslash \},\; \backslash \{b,\; c\backslash \}\; \backslash \},$

$\backslash \{\; \backslash \{b\backslash \},\; \backslash \{a,\; c\backslash \}\; \backslash \},$

$\backslash \{\; \backslash \{c\backslash \},\; \backslash \{a,\; b\backslash \}\; \backslash \},$

$\backslash \{\; \backslash \{a,\; b,\; c\backslash \}\; \backslash \}.$

As suggested by the set notation above, the ordering of subsets within the family is not considered; Weak ordering are counted by a different sequence of numbers, the ordered Bell numbers. $B\_0$ is 1 because there is exactly one partition of the empty set. This partition is itself the empty set; it can be interpreted as a family of subsets of the empty set, consisting of zero subsets. It is vacuous truth that all of the subsets in this family are non-empty subsets of the empty set and that they are pairwise disjoint subsets of the empty set, because there are no subsets to have these unlikely properties.

The partitions of a set bijection with its equivalence relations. These are that are reflexive, symmetric, and transitive. The equivalence relation corresponding to a partition defines two elements as being equivalent when they belong to the same partition subset as each other. Conversely, every equivalence relation corresponds to a partition into equivalence classes.

Therefore, the Bell numbers also count the equivalence relations.

---

Factorizations If a number $N$ is a squarefree positive integer, meaning that it is the product of some number $n$ of distinct , then $B\_n$ gives the number of different multiplicative partitions of $N$. These are of $N$ into numbers greater than one, treating two factorizations as the same if they have the same factors in a different order. credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909). For instance, 30 is the product of the three primes 2, 3, and 5, and has $B\_3$ = 5 factorizations:

$30\; =\; 2\backslash times\; 15=3\backslash times\; 10=5\backslash times\; 6=2\backslash times\; 3\backslash times\; 5$

---

Rhyme schemes The Bell numbers also count the of an n-line poem or stanza. A rhyme scheme describes which lines rhyme with each other, and so may be interpreted as a partition of the set of lines into rhyming subsets. Rhyme schemes are usually written as a sequence of Roman letters, one per line, with rhyming lines given the same letter as each other, and with the first lines in each rhyming set labeled in alphabetical order. Thus, the 15 possible four-line rhyme schemes are AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.

---

Permutations The Bell numbers come up in a card shuffling problem mentioned in the addendum to . If a deck of n cards is shuffled by repeatedly removing the top card and reinserting it anywhere in the deck (including its original position at the top of the deck), with exactly n repetitions of this operation, then there are n ⁿ different shuffles that can be performed. Of these, the number that return the deck to its original sorted order is exactly B_n. Thus, the probability that the deck is in its original order after shuffling it in this way is B_n/ n ⁿ, which is significantly larger than the 1/ n! probability that would describe a uniformly random permutation of the deck.

Related to card shuffling are several other problems of counting special kinds of that are also answered by the Bell numbers. For instance, the nth Bell number equals the number of permutations on n items in which no three values that are in sorted order have the last two of these three consecutive. In a notation for generalized permutation patterns where values that must be consecutive are written adjacent to each other, and values that can appear non-consecutively are separated by a dash, these permutations can be described as the permutations that avoid the pattern 1-23. The permutations that avoid the generalized patterns 12-3, 32-1, 3-21, 1-32, 3-12, 21-3, and 23-1 are also counted by the Bell numbers. The permutations in which every 321 pattern (without restriction on consecutive values) can be extended to a 3241 pattern are also counted by the Bell numbers. However, the Bell numbers grow too quickly to count the permutations that avoid a pattern that has not been generalized in this way: by the (now proven) Stanley–Wilf conjecture, the number of such permutations is singly exponential, and the Bell numbers have a higher asymptotic growth rate than that.

---

Triangle scheme for calculations The Bell numbers can easily be calculated by creating the so-called Bell triangle, also called Aitken's array or the Peirce triangle after Alexander Aitken and Charles Sanders Peirce.

1. Start with the number one. Put this on a row by itself. ($x\_\{0,1\}\; =\; 1$)
2. Start a new row with the rightmost element from the previous row as the leftmost number ($x\_\{i,1\}\; \backslash leftarrow\; x\_\{i-1,\; r\}$ where r is the last element of ( i − 1)-th row)
3. Determine the numbers not on the left column by taking the sum of the number to the left and the number above the number to the left, that is, the number diagonally up and left of the number we are calculating $(\; x\_\{i,j\}\; \backslash leftarrow\; x\_\{i,j-1\}\; +\; x\_\{i-1,j-1\}\; )$
4. Repeat step three until there is a new row with one more number than the previous row (do step 3 until $j\; =\; r\; +\; 1$)
5. The number on the left hand side of a given row is the Bell number for that row. ($B\_i\; \backslash leftarrow\; x\_\{i,1\}$)

Here are the first five rows of the triangle constructed by these rules:

$\backslash begin\{array\}\{l\}$

 1 \\
 1 &  2 \\
 2 &  3 &  5 \\
 5 &  7 & 10 & 15 \\
15 &  20 &  27 &  37 & 52
     

\end{array}

The Bell numbers appear on both the left and right sides of the triangle.

---

Properties

---

Summation formulas The Bell numbers satisfy a recurrence relation involving binomial coefficients:

$B\_\{n+1\}=\backslash sum\_\{k=0\}^\{n\}\; \backslash binom\{n\}\{k\}\; B\_k.$

It can be explained by observing that, from an arbitrary partition of n + 1 items, removing the set containing the first item leaves a partition of a smaller set of k items for some number k that may range from 0 to n. There are $\backslash tbinom\{n\}\{k\}$ choices for the k items that remain after one set is removed, and B_k choices of how to partition them.

A different summation formula represents each Bell number as a sum of Stirling numbers of the second kind

$B\_n=\backslash sum\_\{k=0\}^n\; \backslash left\backslash \; \backslash left(\; \backslash frac\{n\}\{W(n)\}\; \backslash right)^\{n\; +\; \backslash frac\{1\}\{2\}\}\; \backslash exp\backslash left(\backslash frac\{n\}\{W(n)\}\; -\; n\; -\; 1\backslash right).$

established the expansion
     

$B\_\{n+h\}\; =\; \backslash frac\{(n+h)!\}\{W(n)^\{n+h\}\}\; \backslash times\; \backslash frac\{\backslash exp(e^\{W(n)\}\; -\; 1)\}\{(2\backslash pi\; B)^\{1/2\}\}\; \backslash times\; \backslash left(\; 1\; +\; \backslash frac\{P\_0\; +\; hP\_1\; +\; h^2P\_2\}\{e^\{W(n)\}\}\; +\; \backslash frac\{Q\_0\; +\; hQ\_1\; +\; h^2Q\_2\; +\; h^3Q\_3\; +\; h^4Q\_4\}\{e^\{2W(n)\}\}\; +\; O(e^\{-3W(n)\})\; \backslash right)$

uniformly for $h\; =\; O(\backslash ln(n))$ as $n\; \backslash rightarrow\; \backslash infty$, where $B$ and each $P\_i$ and $Q\_i$ are known expressions in $W(n)$.

The asymptotic expression

$$

\begin{align} \frac{\ln B_n}{n} & = \ln n - \ln \ln n - 1 + \frac{\ln \ln n}{\ln n} + \frac{1}{\ln n} + \frac{1}{2}\left(\frac{\ln \ln n}{\ln n}\right)^2 + O\left(\frac{\ln \ln n}{(\ln n)^2} \right) \\ & {} \qquad \text{as }n\to\infty \end{align}

was established by .

---

Bell primes

raised the question of whether infinitely many Bell numbers are also [[prime number]]s. These are called '''Bell primes'''. The first few Bell primes are:
     

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837

corresponding to the indices 2, 3, 7, 13, 42 and 55 . The next Bell prime is B₂₈₄₁, which is approximately 9.30740105 × 10⁶⁵³⁸.

---

History The Bell numbers are named after Eric Temple Bell, who wrote about them in 1938, following up a 1934 paper in which he studied the Bell polynomials. Bell did not claim to have discovered these numbers; in his 1938 paper, he wrote that the Bell numbers "have been frequently investigated" and "have been rediscovered many times". Bell cites several earlier publications on these numbers, beginning with which gives Dobiński's formula for the Bell numbers. Bell called these numbers "exponential numbers"; the name "Bell numbers" and the notation B_n for these numbers was given to them by .. However, Rota gives an incorrect date, 1934, for .

The first exhaustive enumeration of set partitions appears to have occurred in medieval Japan, where (inspired by the popularity of the book The Tale of Genji) a parlor game called genjikō sprang up, in which guests were given five packets of incense to smell and were asked to guess which ones were the same as each other and which were different. The 52 possible solutions, counted by the Bell number B₅, were recorded by 52 different diagrams, which were printed above the chapter headings in some editions of The Tale of Genji. and also mention the connection between Bell numbers and The Tale of Genji, in less detail.

In Srinivasa Ramanujan's second notebook, he investigated both Bell polynomials and Bell numbers. Early references for the Bell triangle, which has the Bell numbers on both of its sides, include and .

---

See also

• Touchard polynomials
• Catalan number
• Stirling number
• Stirling numbers of the first kind

---

Notes

• .
• .
• .
• (2025). 9780486446035, Dover. . ISBN 9780486446035
• (1996). 9780387979939, Springer. . ISBN 9780387979939
• Reprinted with an addendum as "The Tinkly Temple Bells", Chapter 2 of Fractal Music, Hypercards, and more ... Mathematical Recreations from Scientific American, W. H. Freeman, 1992, pp. 24–38
• L. Lovász (1993). 9780821869475, North-Holland. . ISBN 9780821869475
• .
• Herbert S. Wilf (1994). 9780127519562, Academic Press. . ISBN 9780127519562

---

External links

Post Comment